// covertree.h
// 04/17/2011: created

#pragma once
#include <vector>
#include "arma_vector.h"
#include "tree.h"

class CoverTree : public Tree
{
protected:
  typedef Tree::dataset_type    dataset_type;
  typedef std::vector<int>      vint_type;
protected:
  double m_radius; // radius = 2^m_radius
  bool m_only_child;
public:
  CoverTree(dataset_type& data);
  CoverTree(CoverTree* parent, int s, int e, double radius, bool only_child);
  ~CoverTree();
  void buildTree();
  double log_radius() const { return m_radius; }
  void findKNN(const vec& query, std::vector<int>& knnIdx, std::vector<double>& minBound, double radius=POSITIVE_INFINITY);
protected:
  int split();
  void swap(int centerIdx, int to) { int tmp = m_idx[m_s+centerIdx]; m_idx[m_s+centerIdx] = m_idx[m_s+to]; m_idx[m_s+to] = tmp; }
  double distance(int i, int j) const { return arma::norm(get(i)-get(j),2); }
};
